package dfs_bfs;

import java.util.*;

public class ls827 {
    public static void main(String[] args) {
        System.out.println(largestIsland(new int[][]{{1,1,0},{1,0,0},{0,1,1}}));
    }

    public static int largestIsland(int[][] grid) {
        int n = grid.length;
        int re = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int index = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 1){
                    int are = dfs2(grid, i, j, index);
                    map.put(index, are);
                    index++;
                    re = Math.max(re, are);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 0){
                    int mianji = 1;
                    Set<Integer> set = new HashSet<>();
                    if(i - 1 >= 0 && grid[i - 1][j] != 0)
                        set.add(grid[i - 1][j]);
                    if(i + 1 < n && grid[i + 1][j] != 0)
                        set.add(grid[i + 1][j]);
                    if(j - 1 >= 0 && grid[i][j - 1] != 0)
                        set.add(grid[i][j - 1]);
                    if(j + 1 < n && grid[i][j + 1] != 0)
                        set.add(grid[i][j + 1]);
                    for (int t : set) {
                        mianji += map.get(t);
                    }
                    re = Math.max(re, mianji);
                }
            }
        }
        return re;
    }

    public static int dfs2(int[][] grid, int i, int j, int index){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1)
            return 0;
        grid[i][j] = index;
        return 1 + dfs2(grid, i - 1, j, index) + dfs2(grid, i + 1, j, index) +
                dfs2(grid, i, j - 1, index) + dfs2(grid, i, j + 1, index);
    }
}
